#include<vector>
#include<iostream>
using namespace std;

namespace mylist
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prve;

		list_node(T x = T())
			:_data(x)
			, _next(nullptr)
			, _prve(nullptr)
		{
		}

	};
	template<class T, class ref,class ptr>

	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, ref, ptr> self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator++(int)
		{
			Node* tmp = _node;
			_node = _node->_next;
			return tmp;
		}
		self& operator--()
		{
			_node = _node->_prve;
			return *this;
		}
		self& operator--(int)
		{
			Node* tmp = _node;
			_node = _node->_prve;
			return tmp;
		}
		ref operator*()
		{
			return _node->_data;
		}
		ptr operator->()
		{
			return &_node->_data;
		}
		bool operator==(const self& compara)
		{
			return _node == compara->_node;
		}
		bool operator!=(const self& compara)
		{
			return _node != compara._node;
		}

	};
	//template<class T>
	//struct list_ben_end
	//{
	//	typedef list_node<T> Node;
	//	Node* _node;
	//	list_ben_end(Node* node)
	//		:_node(node)
	//	{}
	//	Node* begin()
	//	{
	//		return _node->_prve;
	//	}
	//	Node* endl()
	//	{
	//		return _node->_next;
	//	}
	//};


	template<class T>
	class list
	{
		typedef list_node<T> node;
		//typedef __list_iterator<T> iterator;

	public:
		typedef __list_iterator<T , T& , T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		void empty_init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prve = _head;

		}
		/*	iterator operator->()
			{
				return
			}*/

		iterator insert(iterator begin, T d1 = T())
		{
			node* cut = begin._node;
			node* newnode = new node(d1);
			node* prve = cut->_prve;
			node* next = cut;
			newnode->_prve = prve;
			newnode->_next = next;
			prve->_next = newnode;
			next->_prve = newnode;
			_size++;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			node* cut = pos._node;
			node* prve = cut->_prve;
			node* next = cut->_next;
			prve->_next = next;
			next->_prve = prve;
			delete[] cut;
			_size--;
			return iterator(next);

		}
		list()
			:_head(nullptr)
		{
			empty_init();
		}
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return (iterator)_head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}
		void push_back(T d1)
		{
			/*	node* cut = new node;
				node* prve = _head->_prve;
				prve->_next = cut;
				cut->_prve = prve;
				_head->_prve = cut;
				cut->_next = _head;
				cut->_data = d1;*/
			insert(end(), d1);
		}
		void pop_back()
		{
			erase(_head->_prve);
		}
		void clear()
		{
			//iterator it = begin();
			while (begin() != end())
			{
				erase(begin());
			}
		}
		size_t size()
		{
			return _size;
		}
	private:
		node* _head;
		size_t _size;
	};

	void list_test()
	{
		list<int> d1;
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);

		list<int>::iterator it = d1.begin();
		while (it != d1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void list_test2()
	{
		list<int> d1;
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);
		d1.push_back(1);

		d1.insert(d1.begin(), 7);
		//list<int>::iterator it = d1.begin();
		for (auto e : d1)
		{
			cout << e << " ";
		}
		cout << endl;

		d1.pop_back();
		list<int>::iterator it = d1.begin();
		while (it != d1.end())
		{
			cout << *it << " ";
			++it;
		}

		cout << endl;
		cout << d1.size() << endl;

		d1.clear();
		while (it != d1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		cout << d1.size() << endl;
	}
	template<typename T>
	void print(const list<T> it)
	{
		
		typename list<T>::const_iterator It = it.begin();
		for (auto e : it)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}